\section{Redes de Boltzmann}

Um outro modelo de redes neurais artificiais muito importante e ainda dentro
do contexto de redes recorrentes s\~{a}o as chamadas \emph{Redes de Boltzmann}.
As id\'{e}ias iniciais deste modelo apareceram em 1983 (Hinton e Sejnowski 
\cite{HINTON8301}) e 1985 (Ackley, Hinton e Sejnowski \cite{HINTON8501})
sendo que este modelo pode ser encarado como uma generaliza\c{c}\~{a}o do
modelo de Hopfield \cite{HOPFIELD8201} principalmente devido \`{a}s seguintes
diferen\c{c}as \cite{KORST8901,HAYKIN9401}:

\begin{itemize}
\item  Permite a utiliza\c{c}\~{a}o de nodos escondidos, dando a rede
capacidade de representar regularidades de ordens mais elevadas.

\item  Os nodos s\~{a}o estoc\'{a}sticos e n\~{a}o mais determin\'{\i}sticos, ou
seja, a mudan\c{c}a de estado do nodo passa a ser dada por uma distribui\c{c}\~{a}o 
de probabilidade. Esta distribui\c{c}\~{a}o de probabilidade, com ra\'{\i}zes 
na mec\^{a}nica estat\'{\i}stica, \'{e} chamada de distribui\c{c}\~{a}o de
Boltzmann e d\'{a} nome ao modelo.

\item  As conex\~{o}es podem ser estruturadas de forma livre desde que
permane\c{c}am sim\'{e}tricas, ou seja, a rede n\~{a}o precisa ser totalmente
interconectada (o que impediria at\'{e} mesmo a exist\^{e}ncia de nodos
escondidos).
\end{itemize}

Devido ao estreito relacionamento deste modelo com o algoritmo \emph{%
Simulated Annealing} \cite{KIRKPATRICK8301} e \emph{Cadeias de Markov} 
\cite{BREIMAN6901}, \'{e}
interessante que se fa\c{c}a uma descri\c{c}\~{a}o destes t\'{o}picos antes.

\subsection{{\em Simulated Annealing} e Metropolis}
\label{LAB-BOLTZ-NET-SIM}

O m\'{e}todo de \emph{Simulated Annealing}, dentro da \'{a}rea de f\'{\i}sica da
mat\'{e}ria condensada, pode ser visto como uma forma de se obter materiais
com um arranjo interno de suas part\'{\i}culas com energia m\'{\i}nima, a
um dada temperatura. Para se conseguir isto, o material deve ser
primeiramente levado ao ponto de fus\~{a}o. Neste estado, as suas part\'{\i}culas 
est\~{a}o organizadas de forma aleat\'{o}ria. Depois, a temperatura deve
ser diminu\'{\i}da lentamente, tanto mais lento quanto for a sua proximidade
da temperatura final. Isto permitir\'{a} que o material tenha as suas part\'{\i}culas 
organizadas como uma rede cristalina, com um m\'{\i}nimo de energia 
\cite{KIRKPATRICK8301}.

Um modelo computacional para descrever este comportamento do sistema f\'{\i}sico, 
a uma dada temperatura, foi proposto em 1953 por Metropolis e colaboradores 
\cite{METROPOLIS5301}. No algoritmo de Metropolis o estado atual do
sistema \'{e} representado por uma valor de energia $E$ e a mudan\c{c}a de um
estado $E_i$ para um outro estado $E_j$ (devido a pequenas perturba\c{c}\~{o}es
no sistema) segue as seguintes regras:

\begin{itemize}
\item  Se a diferen\c{c}a de energia $E_j-E_i$ \'{e} negativa ou zero, o novo
estado $j$ \'{e} aceito.

\item  Se a diferen\c{c}a de energia $E_j-E_i$ \'{e} positiva, a aceita\c{c}\~{a}o
do novo estado passa a ser regida pela seguinte probabilidade \cite
{METROPOLIS5301}:
\end{itemize}

\begin{equation}
\exp \left( \frac{E_i-E_j}{k_BT}\right)
\end{equation}

Onde $T$ \'{e} a temperatura do sistema e $k_B$ representa a constante de
Boltzmann.

Al\'{e}m disso, se um n\'{u}mero suficiente de transi\c{c}\~{o}es de estado \'{e}
feito de forma que, em cada temperatura, o sistema alcance o equil\'{\i}brio
t\'{e}rmico, a distribui\c{c}\~{a}o de Boltzmann pode ent\~{a}o ser
utilizada para descrever a probabilidade do estado $i$ ter energia $E_i$, a
uma determinada temperatura $T$. Esta distribui\c{c}\~{a}o \'{e}
representada por \cite{KORST8901}:

\begin{equation}
P_T\left\{ X=i\right\} =\frac 1{Z\left( T\right) }\exp \left( \frac{-E_i}{%
k_bT}\right)
\end{equation}

Neste caso, $X$ \'{e} a vari\'{a}vel aleat\'{o}ria e $Z\left( T\right) $, tamb\'{e}m
chamado de \emph{fun\c{c}\~{a}o de parti\c{c}\~{a}o}, representa um somat\'{o}rio
realizado sobre todos os estados poss\'{\i}veis do sistema com energia $E_i$
e temperatura $T$, descrito por \cite{KORST8901}:

\begin{equation}
Z\left( T\right) =\sum\limits_j\exp \left( \frac{-E_j}{k_BT}\right)
\end{equation}

J\'{a} o algoritmo \emph{Simulated Annealing}, proposto por Kirkpatick, Gelatt
e Vecchi em 1983 \cite{KIRKPATRICK8301}, generaliza o algoritmo de
Metropolis ao criar uma depend\^{e}ncia temporal da temperatura. Dessa forma,
as mudan\c{c}as de estado ocorrem at\'{e} que o sistema alcance o equil\'{\i}brio 
t\'{e}rmico para uma dada temperatura. Depois a temperatura \'{e}
diminu\'{\i}da segundo um programa de resfriamento e ent\~{a}o volta-se \`{a}
fase de itera\c{c}\~{o}es sobre os estados. Este processo continua at\'{e} que o
crit\'{e}rio de converg\^{e}ncia usado seja obedecido.

A escolha de um programa de resfriamento adequado \'{e} crucial para a
determina\c{c}\~{a}o de uma boa solu\c{c}\~{a}o. Geman e Geman \cite{GEMAN8401}
apresentam uma prova da converg\^{e}ncia do algoritmo para um programa de
resfriamento dado pela seguinte express\~{a}o:

\begin{equation}
T_k\geq \frac{T_0}{\log \left( 1+k\right) }  \label{EQGIBBS}
\end{equation}

Onde $T_0$ \'{e} a temperatura inicial (que deve ser suficientemente grande) e 
$T_k$ \'{e} o valor da temperatura na $k$-\'{e}sima itera\c{c}\~{a}o do algoritmo.
O inconveniente \'{e} que este programa de resfriamento se revela muito lento
para aplica\c{c}\~{o}es pr\'{a}ticas \cite{HAYKYN9401}.

Kirkpatrick n\~{a}o apresenta nenhuma f\'{o}rmula espec\'{\i}fica para o
resfriamento, mas evidencia algumas regras \'{u}teis na determina\c{c}\~{a}o do
programa de resfriamento \cite{HAYKYN9401}:

\begin{itemize}
\item  A temperatura inicial deve ser escolhida grande o suficiente para
cobrir todas as poss\'{\i}veis transi\c{c}\~{o}es.

\item  Quando n\~{a}o se consegue alcan\c{c}ar um determinado n\'{u}mero m\'{\i}nimo de
transi\c{c}\~{o}es de estado durante as \'{u}ltimas tr\^{e}s temperaturas, pode-se
considerar que a temperatura final foi alcan\c{c}ada. Um n\'{u}mero de transi\c{c}\~{o}es 
em torno de dez \'{e} citado como m\'{\i}nimo.

\item  Em geral, a temperatura \'{e} diminu\'{\i}da exponencialmente, mas um
decrescimento linear, como mostrado abaixo, tamb\'{e}m pode ser experimentado:
\end{itemize}

\[
T_k=\alpha T_{k-1}\,\,\,\,\,\,\,\,\,\,\,\,\,k=1,2,\ldots 
\]

Neste caso, $\alpha $ deve apresentar valores ligeiramente menores que 1.

Uma das caracter\'{\i}sticas importantes do \emph{Simulated Annealing} est\'{a}
relacionada com o fato de se poder escapar de m\'{\i}nimos locais. Isto \'{e}
poss\'{\i}vel uma vez que mudan\c{c}as para estados de maior energia podem
acontecer, j\'{a} que estas mudan\c{c}as s\~{a}o regidas por probabilidades e
n\~{a}o por regras fixas. Outra caracter\'{\i}stica inerente ao m\'{e}todo \'{e} a
estrat\'{e}gia de \emph{``dividir-e-conquistar''}, ou seja, \`{a} medida que o
sistema evolui, melhorias sucessivas s\~{a}o obtidas \`{a} partir da anterior,
refinando cada vez mais a solu\c{c}\~{a}o.

Finalmente, a exist\^{e}ncia de um paralelo entre o sistema f\'{\i}sico e um
problema de otimiza\c{c}\~{a}o, como mostrado por Korst e Aarts \cite{KORST8901}%
, ir\'{a} permitir que o algoritmo {\em Simulated Annealing} seja aplicado na
resolu\c{c}\~{a}o de problemas de otimiza\c{c}\~{a}o. Em linhas gerais, as
semelhan\c{c}as s\~{a}o as seguintes:

\begin{itemize}
\item  Os estados do sistema f\'{\i}sico passam a ser representados por
solu\c{c}\~{o}es para problemas de otimiza\c{c}\~{a}o

\item  A fun\c{c}\~{a}o de energia \'{e} substitu\'{\i}da por uma fun\c{c}\~{a}o de custo.

\item  Como o conceito de temperatura pode n\~{a}o existir no problema de
otimiza\c{c}\~{a}o $k_BT$ \'{e} trocado por um par\^{a}metro de
controle $c$, respons\'{a}vel por estabelecer uma analogia entre o problema de
otimiza\c{c}\~{a}o e o processo de resfriamento existente no \emph{Simulated
Annealing}.
\end{itemize}

\subsection{Cadeias de Markov}

O formalismo matem\'{a}tico capaz de descrever as transi\c{c}\~{o}es de estado
presentes no algoritmo {\em Simulated Annealing} \'{e} conhecido como \emph{Cadeias
de Markov}, sendo inicialmente desenvolvida por Feller \cite{FELLER6801}. O
livro de Korst e Aarts \cite{KORST8901} se torna bastante relevante como
refer\^{e}ncia ao abordar o tema com um direcionamento para \emph{Simulated
Annealing}, sendo utilizado como base para as pr\'{o}ximas equa\c{c}\~{o}es.
Outra refer\^{e}ncia interessante, de car\'{a}ter mais aplicado, pode ser
encontrada em Breiman \cite{BREIMAN6901}.

Basicamente, uma cadeia de Markov pode ser entendida como:

\begin{description}
\item[Cadeia de markov:]
Uma cadeia de Markov \'{e} uma sequ\^{e}ncia de estados onde a probabilidade de
se ter um determinado estados depende unicamente do estados anterior \cite
{KORST8901}. Sendo $X\left( k\right) $ uma vari\'{a}vel aleat\'{o}ria, a
probabilidade de transi\c{c}\~{a}o de um estado $i$ qualquer para um estado $j$%
, na $k$-\'{e}sima itera\c{c}\~{a}o, pode ser dada por:
\end{description}

\begin{equation}
P_{ij}\left( k\right) =P\left\{ X\left( k\right) =j\,\,|\,\,X\left(
k-1\right) =i\right\}
\end{equation}

J\'{a} a probabilidade de se ter um estado $i$ na $k$-\'{e}sima itera\c{c}\~{a}o
\'{e} representado como a seguir:

\begin{equation}
a_i\left( k\right) =P\left\{ X\left( k\right) =i\right\}
\end{equation}

sendo que $a_i\left( k\right) $ \'{e} descrito por meio de uma recurs\~{a}o:

\begin{equation}
a_i\left( k\right) =\sum_la_l\left( k-1\right) P_{li}\left( k\right)
\end{equation}

No {\em Simulated Annealing}, as v\'{a}rias itera\c{c}\~{o}es que ocorrem a uma dada
temperatura s\~{a}o descritas por uma cadeia de Markov, ou seja, o estado
seguinte depende apenas do estado atual. Ao se usar cadeias de Markov para o
modelo, pode-se provar a converg\^{e}ncia assint\'{o}tica do algoritmo. Esta
prova, um pouco extensa, pode ser encontrada em \cite{KORST8901}.
Basicamente, ela afirma que depois de um grande n\'{u}mero de itera\c{c}\~{o}es,
o algoritmo converge assint\'{o}ticamente para o conjunto \'{o}timo de solu\c{c}\~{o}es 
($S_{opt}$). Matematicamente:

\[
\lim_{k\rightarrow \infty }P\left\{ X\left( k\right) \in S_{opt}\right\} =1
\]


